from collections import defaultdict
import pandas as pd

global f


class Stack(object):
    def __init__(self):
        self.__list = []
    
    def push(self, item):
        self.__list.append(item)
    
    def pop(self):
        return self.__list.pop()
    
    def top(self):
        if self.__list:
            return self.__list[-1]
        return None
    
    def is_empty(self):
        return self.__list == []
    
    def size(self):
        return len(self.__list)
    
    def show(self):
        return ''.join(self.__list)


pd.set_option('display.max_columns', None)
pd.set_option('display.max_rows', None)
pd.set_option('display.width', 500)

gramma = open("../test_data/gramma.txt", 'r', encoding='UTF-8')

vt = ['i', '(', ')', '+', '-', '*', '/', 'epsilon', '#']
vn = ['E', 'T', "E’", "T’", 'F', 'A', 'M']
startCode = vn[0]

first = defaultdict(set)
follow = defaultdict(set)


def split_gramma(gramma):
    stack = []
    for i in gramma:
        i = i.split(' ')
        ss = i[0]
        j = 1
        while j < len(i):
            if i[j] == "->":
                break
            j += 1
        j += 1
        while j < len(i):
            if i[j][-1] == '\n':
                i[j] = i[j][0:-1]
            if i[j] != '|':
                ss += " " + i[j]
            else:
                stack.append(ss.split(' '))
                ss = i[0]
            j += 1
        stack.append(ss.split(' '))
    return stack


productions = split_gramma(gramma)

repr(productions)
strG = ""
for aG in productions:
    strG += aG[0]
    strG += " -> "
    for w in aG[1:]:
        strG += w + " "
    strG += "\n"

f3 = open("ll_1_output.txt", 'w+', encoding='UTF-8')
f3.write(strG)
f3.write("\n\n")


def getFirst(curVn):
    if first[curVn] != set():
        return first[curVn]
    for curPro in productions:
        if curPro[0] == curVn:
            if curPro[1] in vt:
                first[curVn].add(curPro[1])
            else:
                if first[curPro[1]] == set():
                    first[curVn] = set(getFirst(curPro[1]))
                else:
                    first[curVn] = set(first[curPro[1]])
    return first[curVn]


def getFollow(curVn):
    if curVn != 'E' and follow[curVn] != set():
        return follow[curVn]
    for curPro in productions:
        l = len(curPro)
        for i in range(1, l):
            if curPro[i] != curVn:
                continue
            if i == l - 1:
                follow[curVn] = set(getFollow(curPro[0]))
                follow[curVn].add('#')
                continue
            if curPro[i + 1] in vt:
                follow[curVn].add(curPro[i + 1])
            elif curPro[i + 1] in vn:
                if 'epsilon' in first[curPro[i + 1]]:
                    follow[curVn] = follow[curVn] | first[curPro[i + 1]]
                    follow[curVn] = follow[curVn] | set(getFollow(curPro[0]))
                    follow[curVn].discard('epsilon')
                else:
                    follow[curVn] = follow[curVn] | first[curPro[i + 1]]
    return follow[curVn]


for now_vn in vn:
    getFirst(now_vn)

follow[startCode].add('#')
for now_vn in vn:
    getFollow(now_vn)

str1 = "First:\n"
for key in first.keys():
    str1 += key
    str1 += ": "
    str1 += str(first[key]) + "\n"
str1 += "\nFollow:\n"
for key in follow.keys():
    str1 += key
    str1 += ": "
    str1 += str(follow[key]) + "\n"

f3.write(str1)
f3.write("\n\n")

dirFirst = defaultdict(set)


def getDirFirst(curPro):
    res = []
    for i in range(1, len(curPro)):
        if curPro[i] in vt:
            res.append(curPro[i])
            break
        elif curPro[i] in vn:
            if 'epsilon' in first[curPro[i]]:
                res.extend(first[curPro[i]])
            else:
                res.extend(first[curPro[i]])
                break
    ress = []
    for i in res:
        if i not in ress:
            ress.append(i)
    return ress


dfData = [[[] for i in range(len(vt))] for i in range(len(vn))]
dfData1 = [["" for i in range(len(vt))] for i in range(len(vn))]

M = pd.DataFrame(data=dfData, index=vn, columns=vt)
outM = pd.DataFrame(data=dfData1, index=vn, columns=vt)


def getM():
    for curPro in productions:
        A = curPro[0]
        dirFirst = getDirFirst(curPro)
        for a in dirFirst:
            if a == 'epsilon':
                continue
            strForm = curPro[0] + "->"
            for w in curPro[1:]:
                strForm += w
            M.loc[A][a].append(curPro)
            outM.loc[A][a] += "    " + strForm
    for curPro in productions:
        A = curPro[0]
        dirFirst = getDirFirst(curPro)
        if 'epsilon' in dirFirst:
            for b in follow[A]:
                strForm = curPro[0] + "->"
                for w in curPro[1:]:
                    strForm += w
                M.loc[A][b].append(curPro)
                outM.loc[A][b] += "    " + strForm


getM()
strM = str(outM)

print(outM)
print(M)
f3.write("predict_table：\n")
f3.write(str(outM))
f3.close()


def getRes(lang):
    global f
    V = lang.split(' ')
    V.append('#')
    l = len(V)
    i = 0
    sta = Stack()
    sta.push('#')
    sta.push('E')
    
    X = sta.top()
    while X != '#':
        a = V[i]
        print("X:" + X)
        print("a:" + a)
        if X == a:
            sta.pop()
            i = i + 1
            print('match: ', a)
        elif X in vt:
            print("error happend! the left of proc is end sym")
            i = i + 1
            f = 1
            continue
        elif not M[a][X]:
            print("error happend! no gramma found")
            i = i + 1
            f = 1
            continue
        elif M[a][X][0] in productions:
            prod = M[a][X][0]
            print("Input  ：", ''.join(V[i:]))
            print("OutPut ：", end='')
            print(prod[0], end=' -> ')
            for rPord in prod[1:]:
                print(rPord, end=" ")
            print()
            sta.pop()
            ll = len(prod)
            for ii in range(ll - 1):
                if prod[ll - ii - 1] != 'epsilon':
                    sta.push(prod[ll - ii - 1])
        X = sta.top()
        print('Stack :', sta.show())
        print()
    
    if f == 1:
        print("wrong")
    elif sta.top() == '#':
        print("true")


sentence = "i + ( i * + i )"
getRes(sentence)
